package xin.javashare.sort;

/**
 * 【基本思想】:
 * 将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。
 * 即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。
 * 要点：设立哨兵，作为临时存储和判断数组边界之用。
 *
 * 【稳定排序算法】
 * 如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。
 * 所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是【稳定】的。
 *
 * 【效率】：
 * 时间复杂度：O（n^2）.
 * 其他的插入排序有二分插入排序，2-路插入排序。
 *
 * 插入的方法一共有三种：
 * 我们可以从左向右扫描序列，找到合适的位置插入；
 * 我们可以从右向左扫描序列，找到合适的位置插入；
 * 对于有序序列我们可以使用折半查找到合适的位置插入。
 */
public class InsertionSort {
    public void insertionSort(int[] array) {
        for (int i = 1,len = array.length; i < len; i++) {
            int temp = array[i];//保存待插入的值
            int j;
            //通过循环，逐个后移一位找到要插入的位置
            for (j = i - 1; j >= 0 && temp < array[j]; j--) {
                array[j + 1] = array[j];
            }

            //当不满足temp < array[j]时，要插入的位置在j后一位
            array[j+1] = temp;//插入待插入的值
        }
    }

    // 另一种写法
    public static void insertionSort2(int[] list) {
        for (int i = 1; i < list.length; i++) {
            if (list[i] < list[i - 1]) {
                int temp = list[i];
                int j = i;

                while (j > 0 && temp < list[j - 1]) {
                    list[j] = list[j - 1]; //向后移动
                    j--;
                }
                list[j] = temp;
            }
        }
    }

    public static void insertionSort3(int[] arr) {
        if (arr == null || arr.length < 2) return;
        int n = arr.length;
        int j,low, high, mid;
        for (int i = 1; i < n; i++) {
            int temp = arr[i];

            low = 0;
            high = i - 1;
            // 二分查找法找到插入的位置
            while (low <= high) {
                mid = low + (high - low) / 2;
                if (temp < arr[mid]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            for (j = i - 1; j > high; j--) {
                arr[j + 1] = arr[j];
            }

            arr[high+1] = temp;
        }
    }
    public static void main(String[] agrs) {
        int a[] = {3,1,5,7,2,4,9,6,10,8};
        InsertionSort  obj=new InsertionSort();
        System.out.println("初始值：");
        obj.print(a);
        obj.insertionSort3(a);
        System.out.println("\n排序后：");
        obj.print(a);
    }

    private void print(int a[]){
        for (int anA : a) {
            System.out.print(anA + " ");
        }
    }
}
